﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using TransformCost.Question;
using System.Collections;

namespace TransformCost.Answer
{
    class Jimson : ITransformCost
    {
        public int GetMinExchanges(int[] source, int[] target)
        {
            //throw new NotImplementedException();
            int steps = 0;
            bool Isfind = false;
        // List<int> s =  source.ToList();
            List<int> tar = target.ToList();
            List<List<int>> list = new List<List<int>>() { source.ToList() };
            List<List<int>> sublist = new List<List<int>>();

            while (!Isfind)
            {
                foreach (List<int> item in list)
                {
                    if (Equeal(item, tar))
                    {
                        Isfind = true;
                        return steps;
                    }
                    else
                    {
                        sublist.AddRange(GenChange(item));
                       
                    }
                }
                steps++;
                list = new List<List<int>>(sublist);
                sublist.Clear();

            }

            return steps;
        }


        public bool Equeal(List<int> source, List<int> target)
        {
            for (int i = 0; i < source.Count; i++)
            {
                if (source[i] != target[i])
                {
                    return false;
                }
            }
            return true;
        }

        public List<List<int>> GenChange(List<int> source)
        {
            List<List<int>> list = new List<List<int>>();
            for (int i = 0; i < source.Count-1; i++)
            {
                List<int> a = new List<int>();
                for (int j = 0; j < source.Count; j++)
                {
                    if (j == i)
                    {
                        a.Add(source[j + 1]);
                    }
                    else
                    {
                        if (j == i + 1)
                        {
                            a.Add(source[j - 1]);
                        }
                        else
                        {
                            a.Add(source[j]);
                        }
                    }
                    
                }
                list.Add(a);
            }
            return list;
        }
    }
}
